package 力扣_树算法.树与链表;

/**
 * @author zx
 * @create 2023-01-16 0:15
 */
public class 二叉搜索树与双向链表_牛客网 {
    /**
     * 非虚拟头节点版
     * 因为牛客网上要求不能创建任何新的结点,所以虚拟头节点版本过不了
     * 为了过面试方便,这几道题统一记住非虚拟头节点版,虽然虚拟头节点版更短
     *
     * 其实和力扣对比,牛客网的这道题不严谨,用我的方法做,它这道题是错的！！！
     */
    TreeNode prev = null;
    TreeNode head = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            return null;
        }
        inOrder(pRootOfTree);
        return head;
    }
    private void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        if(prev != null) {
            prev.right = root;
        }else{
            head = root;
        }
        root.left = prev;
        prev = root;
        inOrder(root.right);
    }

    /**
     * @return 虚拟头节点版,但是牛客网过不了
     */
    //TreeNode prev = null;
    public TreeNode Convert2(TreeNode pRootOfTree) {
        if(pRootOfTree==null) {
            return null;
        }
        TreeNode dummy = new TreeNode(-1);
        prev = dummy;
        inOrder(pRootOfTree);
        return dummy.right;
    }
    private void inOrder2(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        prev.right = root;
        root.left = prev;
        prev = root;
        inOrder(root.right);
    }
}